//
// Created by 陈磊 on 16/8/26.
//

#include <random>
#include <iostream>
#include "LinkedListCode.h"

void LinkedListCode::reverseLinkedList(LinkedNode *head) {
    if(head==NULL || head->next==NULL){
        return  ;
    }
    //只有一个元素
    if(head->next->next == NULL){
        return; ;
    }
    //插头法
    LinkedNode* curNode = head->next->next ;
    LinkedNode* pilotNode = head->next;
    while(curNode->next != NULL){
        pilotNode->next = curNode->next ;
        curNode->next = head->next ;
        head->next = curNode ;
        curNode = pilotNode->next ;
    }
    pilotNode->next = NULL ;
    curNode->next = head->next ;
    head->next = curNode ;
}

LinkedNode* LinkedListCode::makeRandomLinkedList(int size) {
    if(size < 0){
        return NULL ;
    }
    //时间种子 间隔时间不够，所以设置的种子其实是一样的。
    //避免这个情况,需要在定义范围和引擎时，将其定义为static 。
    static std::default_random_engine generator(time(NULL));
    static std::uniform_int_distribution<int> dis(0,100);
    static auto dice= std::bind(dis, generator);
    LinkedNode* head = new LinkedNode() ;
    head->value = size ;
    LinkedNode* preNode =head  ;
    for(int i=0;i<size;i++) {
        LinkedNode *curNode = new LinkedNode();
        curNode->value = dice();
        curNode->next =NULL ;
        preNode->next = curNode ;
        preNode = curNode ;
    }
    preNode->next = NULL ;
    return head ;
}

void LinkedListCode::quickSort(LinkedNode *pHead,LinkedNode *pEnd) {
    if(pHead==NULL || pHead->next==NULL || pEnd == NULL){
        return ;
    }
    LinkedNode* prePilotdNode = this->_getPartition(pHead,pEnd) ;
    if(prePilotdNode!= NULL) {
        this->quickSort(pHead, prePilotdNode);
        this->quickSort(prePilotdNode->next, pEnd);
    }
}

LinkedNode* LinkedListCode::_getPartition(LinkedNode *pHead, LinkedNode *pEnd) {
    if(pHead==NULL || pHead->next == NULL || pHead == pEnd ){
        return NULL;
    }
    if(pHead->next == pEnd){
        return pHead ;
    }
    //第一个节电为头结点
    //从第二个节点开始作为pilot
    LinkedNode* pilotNode = pHead->next ;
    int pilotValue = pilotNode->value ;

    LinkedNode* curNode = pHead->next->next  ;
    LinkedNode* preCurNode = pHead->next ,*prePilotNode = pHead ;
    bool onlyOnce = true ;
    while(curNode!=NULL && preCurNode != pEnd){
        if(curNode->value < pilotValue){
            //发现比pilotValue小插入头部
            preCurNode->next = curNode->next ;
            curNode->next = pHead->next ;
            pHead->next = curNode ;
            if(onlyOnce) {
                prePilotNode = curNode;
                onlyOnce = false ;
            }
            curNode = preCurNode->next  ;
        }else {
            preCurNode = curNode;
            curNode = curNode->next;
        }
    }
    return prePilotNode ;
}

void LinkedListCode::printLinkedList(LinkedNode *head) {
    if(head==NULL || head->next==NULL){
        std::cout << "printLinkedList : LinkedList is NULL or there is no element" << std::endl ;
        return;
    }
    LinkedNode* curNode = head->next ;
    while(curNode->next != NULL){
        std::cout <<  curNode->value << " -> "  ;
        curNode = curNode->next ;
    }
    std::cout <<  curNode->value  << std::endl ;
}

void LinkedListCode::mergeTwoSortedLinkedListToFirst(LinkedNode *pHeadOne, LinkedNode *pHeadTwo) {
    if(pHeadOne==NULL || pHeadTwo==NULL){
        std::cout << "mergeTwoSortedLinkedListToFirst : LinkedList is NULL , return" << std::endl ;
        return ;
    }
    pHeadOne->value = pHeadOne->value + pHeadTwo->value ;
    if(pHeadOne->next ==NULL) {
        pHeadOne->next = pHeadTwo->next;
        return;
    }
    LinkedNode* pOneCur = pHeadOne->next ,*preOneCur = pHeadOne ;
    LinkedNode* pTwoCur = pHeadTwo->next ,*preTwoCur = pHeadTwo;
    while(pOneCur!=NULL && pTwoCur!=NULL){
        if(pTwoCur->value < pOneCur->value){
            preTwoCur->next = pTwoCur->next ;
            pTwoCur->next = pOneCur ;
            preOneCur->next = pTwoCur ;

            preOneCur = pTwoCur ;
            pTwoCur = preTwoCur->next ;
        } else{
            preOneCur = pOneCur ;
            pOneCur = pOneCur->next ;
        }
    }
    LinkedNode* pOneLast = preOneCur ;
    if(pTwoCur != NULL){
        while(pTwoCur!=NULL){
            pOneLast->next = pTwoCur ;
            pOneLast = pTwoCur ;
            pTwoCur = pTwoCur->next ;
        }
    }

}

LinkedNode* LinkedListCode::getTailNode(LinkedNode *head) {
    if(head==NULL || head->next==NULL){
        return head;
    }
    LinkedNode* curNode = head->next ;
    while(curNode->next!=NULL){
        curNode = curNode->next ;
    }
    return curNode ;
}

LinkedNode* LinkedListCode::findFirstPublicNode(LinkedNode *pHeadOne, LinkedNode *pHeadTwo) {
    if(pHeadOne==NULL || pHeadTwo==NULL || pHeadOne->next==NULL || pHeadTwo->next==NULL){
        std::cout << "findFirstPublicNode : LinkedList is NULL  or have no element, return NULL" << std::endl ;
        return NULL;
    }
    int oneSize = 0 ,twoSize=0 ;
    LinkedNode* oneCurNode = pHeadOne->next ,* twoCurNode = pHeadTwo->next ;
    while(oneCurNode!=NULL){
        oneSize++ ;
        oneCurNode = oneCurNode->next ;
    }
    while(twoCurNode!=NULL){
        twoSize++ ;
        twoCurNode = twoCurNode->next ;
    }
    LinkedNode * pLongCurNode  = oneSize >= twoSize ? pHeadOne->next : pHeadTwo->next  ;
    LinkedNode * pShortCurNode = oneSize < twoSize ? pHeadOne->next : pHeadTwo->next  ;
    int gap = oneSize > twoSize ?  oneSize-twoSize : twoSize - oneSize ;
    //长链表cur指针推进gap长度
    while(gap!=0 && pLongCurNode!=NULL){
        pLongCurNode = pLongCurNode->next ;
        gap -- ;
    }
    //两个链表从cur指针开始到尾节点长度相同,开始同步遍历
    while(pLongCurNode!=NULL && pShortCurNode!=NULL ){
        if(pLongCurNode == pShortCurNode) {
            return pLongCurNode;
        }
        pLongCurNode=pLongCurNode->next ;
        pShortCurNode=pShortCurNode->next ;
    }
    //没有公共节点
    return  NULL ;
}

void LinkedListCode::deleteNodeSubtle(LinkedNode *pHead, LinkedNode *toBeDeleted) {
    //思路:     交换toBeDeleted与toBeDeleted->next的元素,这样可以获取pre和cur指针,删除下一个Node
    if(pHead==NULL || pHead->next==NULL || toBeDeleted==NULL){
        return ;
    }
    //删除的是尾节点,单独处理需要O(n)
    if(toBeDeleted->next == NULL){
        LinkedNode* curNode = pHead->next ;
        while(curNode->next!=toBeDeleted && curNode->next!=NULL){
            curNode = curNode->next ;
        }
        curNode->next = NULL ;
        delete toBeDeleted ;
    }else {
        LinkedNode *curNode = toBeDeleted->next;
        LinkedNode *preNode = toBeDeleted;
        preNode->next = curNode->next;
        delete curNode;
    }
}

bool LinkedListCode::haveCircle(LinkedNode *pHead) {
    //思路:   两个指针、一快一慢。如果有环,快指针会追上满指针。
    if(pHead==NULL || pHead->next==NULL){
        return NULL ;
    }
    LinkedNode* pQuick = pHead->next->next ;
    LinkedNode* pSlow = pHead->next ;
    while(pQuick!=NULL && pSlow!=NULL){
        if(pQuick == pSlow){
            return true ;
        }
        if(pQuick->next != NULL)
            pQuick = pQuick->next->next ;
        else
            return false ;
        pSlow = pSlow->next ;
    }
    return false ;
}

void LinkedListCode::testMain() {
    LinkedListCode linkedListCode  ;
    LinkedNode* linkedList = linkedListCode.makeRandomLinkedList(0) ;
    LinkedNode* linkedList2 = linkedListCode.makeRandomLinkedList(10) ;
    linkedListCode.printLinkedList(linkedList) ;
    linkedListCode.printLinkedList(linkedList2) ;
//
//    LinkedNode* pTail = linkedListCode.getTailNode(linkedList) ;
//    linkedListCode.quickSort(linkedList,pTail) ;
//
//    LinkedNode* pTail2 = linkedListCode.getTailNode(linkedList2) ;
//    linkedListCode.quickSort(linkedList2,pTail2) ;
//
//    linkedListCode.printLinkedList(linkedList) ;
//    linkedListCode.printLinkedList(linkedList2) ;
//
//
//    linkedListCode.mergeTwoSortedLinkedListToFirst(linkedList,linkedList2) ;
//
//    linkedListCode.printLinkedList(linkedList) ;
//    linkedListCode.reverseLinkedList(linkedList) ;
//    linkedListCode.printLinkedList(linkedList) ;
//
//    LinkedNode* llong = linkedListCode.makeRandomLinkedList(11) ;
//    LinkedNode* lshort = linkedListCode.makeRandomLinkedList(8) ;
//    LinkedNode* lpublic = linkedListCode.makeRandomLinkedList(4) ;
//
//    linkedListCode.getTailNode(llong)->next = lpublic ;
//    linkedListCode.getTailNode(lshort)->next = lpublic ;
//    linkedListCode.printLinkedList(llong) ;
//    linkedListCode.printLinkedList(lshort) ;
//    LinkedNode* fpn = linkedListCode.findFirstPublicNode(lshort,llong) ;
//    linkedListCode.printLinkedList(fpn) ;


//    linkedListCode.deleteNodeSubtle(linkedList2,linkedList2->next->next->next) ;
//    linkedListCode.printLinkedList(linkedList2) ;
//    linkedListCode.deleteNodeSubtle(linkedList2,linkedListCode.getTailNode(linkedList2)) ;
//    linkedListCode.printLinkedList(linkedList2) ;

    linkedListCode.getTailNode(linkedList2)->next = linkedList2->next->next ;
    std::cout << linkedListCode.haveCircle(linkedList2) << std::endl ;
}